
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1808. -- [Ioi2007]training 训练路径
</title><center><h2>1808: [Ioi2007]training 训练路径
</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>19&nbsp;&nbsp;<span class=green>Solved: </span>11<br>[<a href='submitpage.php?id=1808'>Submit</a>][<a href='problemstatus.php?id=1808'>Status</a>][<a href='bbs.php?id=1808'>Discuss</a>]</center><h2>Description</h2><div class=content>马克(Mirko)和斯拉夫克(Slavko)正在为克罗地亚举办的每年一次的双人骑车马拉松赛而紧张训练。他们需要选择一条训练路径。

他们国家有N个城市和M条道路。每条道路连接两个城市。这些道路中恰好有N-1条是铺设好的道路，其余道路是未经铺设的土路。幸运的是，每两个城市之间都存在一条由铺设好的道路组成的通路。换句话说，这N个城市和N-1条铺设好的道路构成一个树状结构。

此外，每个城市最多是10条道路的端点。

一条训练路径由某个城市开始，途经一些道路后在原来起始的城市结束。因为马克和斯拉夫克喜欢去看新城市，所以他们制定了一条规则：绝不中途穿越已经去过的城市，并且绝不在相同的道路上骑行两次（不管方向是否相同）。训练路径可以从任何一个城市开始，并且不需要访问所有城市。

显然，坐在后座的骑行者更为轻松，因为坐在前面的可以为他挡风。为此，马克和斯拉夫克在每个城市都要调换位置。为了保证他们的训练强度相同，他们要选择一条具有偶数条道路的路径。

马克和斯拉夫克的竞争者决定在某些未经铺设的土路上设置路障，使得他们两人不可能找到满足上述要求的训练路径。已知在每条土路上设置路障都有一个费用值（一个正整数），并且竞争者不能在铺设好的道路上设置路障。
任务
给定城市和道路网的描述，写一个程序计算出为了使得满足上述要求的训练路径不存在，而需要的设置路障的最小总费用。
</div><h2>Input</h2><div class=content>输入的第一行包含两个整数N和M，（2≤N≤1000，N-1≤M≤5000），分别表示城市和道路的个数。

接下来的M行每行包含3个整数A, B和C（1≤A≤N, 1≤B≤N, 0≤C≤10 000）, 用来描述一条道路。A和B是不同的整数，表示由这条道路直接相连的两个城市。对于铺设好的道路C是0；对于土路，c是在该条路上设置路障所需的费用值。

每个城市最多是10条道路的端点。任意两个城市都不会有多于一条直接相连的道路。

</div><h2>Output</h2><div class=content>输出包含一个整数，表示求出的最小总费用。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5 8 <br />
2 1 0 <br />
3 2 0 <br />
4 3 0 <br />
5 4 0 <br />
1 3 2 <br />
3 5 2 <br />
2 4 5 <br />
2 5 1 <br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>5 </span></div><h2>HINT</h2>
			<div class=content><p><img border="0" src="images/1808.jpg"> </p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1808'>Submit</a>][<a href='problemstatus.php?id=1808'>Status</a>][<a href='bbs.php?id=1808'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
